1 I B HAHY
OF THE
U N IVERSITY
Of ILLINOIS
510,84
I^6r
no. 156163
c o p 2
r
^ATHEMP •
DIGITAL COMPUTER LABORATORY
UNIVERSITY OF ILLINOIS
URBANA, ILLINOIS
REPORT NO, 162
MINIMAL THREEVARIABLE "NOR" AND "NAND" LOGIC CIRCUITS
by
Robert Allan Smith
May 15, 196k
(This work is being submitted in partial fulfillment of the requirements for
the Degree of Master of Science. )
MTHEMA1
LIBRARY
Digitized by the Internet Archive
in 2013
http://archive.org/details/minimalthreevari162smit
ACKNOWLEDGMENT
The author wishes to express his sincere thanks to Professor
To A, Murrell, his thesis advisor, for assistance in the preparation of this
thesis.
Return this book on or before the
Latest Date stamped below.
Theft, mutilation, and underlining of books
are reasons for disciplinary action and may
result in dismissal from the University.
University of Illinois Library
MAR B W87
L161— O1096
TABLE OF CONTENTS
Page
1. INTRODUCTION 1
2. DESCRIPTION OF THE PROGRAM 3
2.1 The Universal Circuit 3
2.2 Generation of Matrices k
2.3 Processing of Matrices 5
3. COMMENTS ON THE RESULTS .......... 6
k. TABLE OF RESULTS ................. 7
5. CIRCUIT DIAGRAMS . 18
6. CONCLUSIONS ...... 20
BIBLIOGRAPHY .... ................ 21
in
MINIMAL THREEVARIABLE "NOR" AND "NANIj" LOGIC CJ
Robert Allan Smith, M.S.
Department of Electrical Engineering
University of Illinois, 196^
This paper presents a table of minimal NOR and NAND combinational
circuits for the 256 logical functions of three variables, assuming complemented
inputs are available. The circuits were found by an exhaustive method, using a
computer. The criteria used for minimality were, first, minimality with respect
to the number of logic elements, and second, minimality with respect to the
total number of inputs to all elements, subject to the first condition. The
results show that all 256 functions can be generated using five or fewer NOR or
NAND elements.
■IV
1. INTRODUCTION
Circuits composed of NOR or NAND elements, while not the fastest type
of circuits, are used extensively, mainly because of their economyone type of
element may be used throughout an entire circuit. Assuming the basic decision
to use such "universal" elements has been made, the main design objective will
usually be to produce either the fastest or the most economical circuit possible.
The fastest NAND circuits, i.e., minimum levels, are obtained by rewriting the
minimumOR polynomial (as obtained by the QuineMcCluskey method) in terms of
the NAND connective, yielding a threelevel logic (twolevel if complemented
inputs are available). Similarly the minimum AND polynomial may be written in
terms of the NOR connective. Circuits obtained in this way are often also mini
mal with respect to the number of logic elements required.
At present there are no known algebraic methods of obtaining absolutely
minimal NOR or NAND circuits, or for that matter, circuits using any other types
of logic elements. Methods such as the QuineMcCluskey method and the Karnaugh
1 3
map method ' give only neartominimal realizations. Recently, however,
2
Hellerman has reported the results of an exhaustive method utilizing a computer.
The criteria used for minimality were, first, minimality with respect to the
number of logic elements, and second, minimality with respect to the total number
of inputs to all elements, subject to the first condition. Complemented inputs
were assumed not available.
In Hellerman ' s approach, a universal circuit configuration was set up
which permitted systematic investigation of all the possible ways of connecting
together a given number of NOR elements . The program began by generating as many
functions as possible using one NOR element and storing the circuit configuration
and the number of inputs required, in memory. Then, all possible configurations
of two NOR elements were considered. If a particular function had been generated
1
previously with fewer elements or with the same number of elements but with
fewer inputs, the configuration under consideration was discarded. If the func
tion had been generated previously with the same number of elements but with more
inputs, the information regarding the configuration and the number of inputs
replaced the previously stored information for that function. The program con
tinued in this way, up to seven NOR elements, and yielded a catalog of minimal
NOR realizations for the 256 logical functions of three variables. Minimal NAND
realizations were derived from the set of NOR realizations.
The results reported in this thesis form an extension of Hellerman's
work. A similar catalog is given, with the difference being that complemented
inputs are assumed available. The same minimality criteria are used. The
results show that with complemented inputs, all 256 functions can be generated
using five or fewer NOR or NAND elements.
2. DESCRIPTION OF THE PROGRAM
The computer program was written in the assembler language SCATRE
and was run on the IBM 709^+, the total running time being approximately
35 minutes. The program considered NAND circuits rather than NOR circuits, and
began with one NAND element, continuing up to four NAND elements,
2.1 The Universal Circuit
The universal circuit which allowed investigation of all possible
configurations of four NAND elements is shown in Fig„ 1.
Inputs
a b c a b c
123^56 7 89
FIGURE 1. THE UNIVERSAL CIRCUIT
Output
Crossover points are either connected or disconnected, indicating which
inputs feed the various elements. The circuit is then representable by a connec
tion matrix, a matrix of ones and zeros, each element of which indicates the
presence or absence of a connection at the corresponding point in the circuit „
A separate computer word was used to represent each row of the matrix. Since
30 ^ 9
each connection point has two possible values, there are 2 ~ 10 possible
3
connection matrices. Many of these will, however, result in useless circui'
and there are a number of restrictions which may be placed on the form of the
connection matrix to eliminate these. Some restrictions are difficult to incor
porate into a program and some effect only a small saving of time. The following
three restrictions were used in the final program:
1. An input and its complement (e.g. , a and a) were not allowed
to be fed into the same NAND element.
2. Columns 1, 2, and 3 were "ordered," i.e., if A, B, and C
represent the values of columns 1, 2, and 3 when considered
as binary numbers, then it was required that
A > B > C
This means that the program investigated only one member
from each of the 80 equivalence classes of functions of
three variables, i.e., one member from each set of con
nection matrices whose members differ only in that they
effect a permutation of input variables.
3. Each element in the circuit had to be "useful," i.e., the
output of every element (except the last) had to feed some
other element.
The number of matrices connecting four NAND elements which will pass
the above restrictions is approximately 5 X 10 > a considerable saving over the
original number.
2.2 Generation of Matrices
The systematic generation of matrices connecting four NANB elements
was carried out as follows. Because of restriction 3j there are only 21 possible
partial matrices consisting of columns 7, 8, and 9° These were stored in memory
to be added to the remaining portion of the matrix. Because of restriction 1,
there are only 27 permissible ways of "filling" the portion of any row up to
column 6. These were similarly stored in 27 words. An outer program loop
selected one of the 21 partial matrices for columns 7> 8, and 9 Inner loops
systematically selected partial rows from the 27 possible ones, such that all
combinations were exhausted. After generation of a particular matrix, columns 1,
2, and 3 were checked for ordering. If ordering was present the matrix was
"processed" to determine what logical function it produced; if not, a new matrix
was generated.
2.3 Processing of Matrices
The processing of a given matrix was the key portion of the program
since it was repeated so many times; hence it had to be made as economical as
possible. The basic method of processing was the same as used by Hellerman,
i.e., the output of the circuit was determined for each of the eight possible
input combinations. The sequence of machine instructions used to accomplish
this was different however, and is thought to be as efficient as possible, A
given input combination was placed in the senseindicator (Si) register. Then
each bit position of the word for row 1 which was a one was compared with the
corresponding bit in the SI register, using the ONT (ontest for indicators)
instruction. If all corresponding positions were also one this meant that the
output of the NAND element in row 1 was zero, and the computer skipped the next
instruction. If any position was zero, this meant that the output of the NAND
element was a one, and the machine executed the next instruction, which placed
(via the OSI instruction) an additional one in the "column7" position of the SI
reigster. This process was then repeated for the remaining rows.
3. COMMENTS ON THE RESULTS
Not all of the 256 functions of three variables were generated by the
circuits containing up to four NAND elements. Circuits for the ten remaining
functions were found and are included in the table of results. They all contain
five NAND elements and hence are minimal with respect to the number of elements,
but they may not be minimal with respect to the number of inputs.
The set of minimal NOR circuits is also given in Table 1. These
were obtained directly from the minimal NAND circuits using the fact that any
minimal NAND circuit realizing a function F(a,b,c) will also represent a minimal
NOR circuit for the function G(a,b,c) where
F(a,b,c) = G(a,b,c)
6
h, TABLE OK RESULTS
Table 1 lists the minimal NOR and NAND realizations for the
256 functions of three variables, assuming complemented inputs are available.
The functions are listed according to an octal number which indicates which
minterms are present in the canonical expansion of the function, Writing a
given octal designation number as an 8bit binary number (filling in left zeros
if necessary), the bits, from left to right, indicate the presence or absence of
the terms abc, abc, abc, abc, abc, abc, abc, abc.
The circuit numbers and the corresponding inputs refer to the circuit
diagrams following the table. A circuit number of zero indicates that the
function requires no NAND elementit is either just a single literal or iden
tically zero or one.
Several functions have two minimal realizations. In such cases the
alternative realization is listed immediately following the main entry.
7
TABLE 1.
Fen.
NAND
Inputs
NOR
Inputs
No.
Expression
Cct.
l
2
3
k
5
6789
Cct.
1
2
3
k
5 6 7 8 9
1
abc
3
a
b
c
2
a
b
c
2
abc
3
a
b
c
2
a
b
c
3
ab
k
a
b
1
a
b
k
abc
3
a
b
c
2
a
b
c
5
ac
k
a
c
1
a
c
6
a(bc+bc)
7
a
b
c
a
b
c
10
b
c
b
c
a
7
a(b+c)
6
b
c
a
5
b
c
a
10
abc
3
a
b
c
2
a
b
c
11
a(bc+bc)
7
a
b
c
a
b
c
10
c
b
b
c
a
12
ac
k
a
c
1
a
c
13
a(b+c)
6
b
c
a
5
c
b
a
Ik
ab
k
a
b
1
a
b
15
a(b+c)
6
c
b
a
5
b
c
a
16
a(b+c)
6
b
c
a
5
b
c
a
IT
a
a
a
20
abc
3
a
b
c
2
a
b
c
21
be
k
b
c
1
b
c
22
b(ac+ac)
7
b
c
a
b
c
a
10
a
c
a
c
b
23
b(a+c)
6
c
a
b
5
a
c
b
24
c ( ab+ab )
7
c
a
b
c
a
b
10
a
b
a
b
c
25
c ( a+b )
6
a
b
c
5
a
b
c
26
abc+abc+abc
11
a
b
c
a
b
c a b c
18
a
b
a
c
b c a b c
27
ab+ac+bc
12
b
c
a
b
c
12
b
c
a
b
c
30
abc+abc
7
a
b
c
a
b
c
15
16
b
b
c
a
a
c
b
a
c a
b c
31
abc+bc
8
b
c
a
b
c
Ik
12
b
a
c
c
a
b
b
b
c
c
32
ac+abc
8
a
c
a
b
c
<
Ik
12
a
b
c
c
b
a
a
a
c
c
33
ac+bc
9
b
c
a
c
9
a
c
b
c
TABLE 1 (CONT'D).
Fcn<
No.
Expression
NAND Inputs N ffl
Cct. 12 3 4 5 6 7 8 9 Cct,
Inputs
123456789
34
45
kG
ab+abc
35
ab+bc
36
a(b+c)+abc
37
a+bc
l+O
abc
l+l
b(ac+ac)
1+2
be
43
b(a+c)
kk
abc+abc
abc+ac
bc+abc
hi
bc+ac
50
abc+abc
51
abc+abc+abc
52
c ( a+b )
53
c(a+b)+ab
54
ab+abc
55
a(b+c)+abc
56
ab+bc
57
a+bc
60
ab
61
b(a+c)
62
b(a+c)
63
b
61+
ab+abc
a b a b c
9
a
b
c
b
13
b
c
a
b
c
a
5
b
c
a
3
b
c
a
7
b
c
a
b
c
a
1+
b
c
6
a
c
b
7
b
c
a
b
c
a
65
ab+ac
8 c a b c a
8 b c a b c
9 b c a c
7 a b c a b c
11 abcabcabc
6 abc
12 a b c a b
8 a b a b c
13 b c a b a c
9 abbe
5 b c a
1+ a b
6 a c b
6 cab
b
8 a b a b c
9 abac
11+
12
9
13
6
2
10
1
5
15
16
ll+
12
11+
12
9
10
18
5
12
11+
12
13
9
6
1
5
5
ik
12
9
a b
c b
b c
b c
b c
c a
c a
c b
c a
c a
c b
c a
b a
b c
a c
b c
a b
a b
a b
b c
a b
b c
b c
a b
c b
a b
a c
a c
b
b a
c a
a b
cab
a a b
b a
a b c a
a
b
cab
b
b c a b
a b c a
b c a
c c a
abc
b b c
a c
abc
a c b c a b c
c
abc
a c b
a a b
abac
b c
a
b
b
c b a
b b a
a c
TABLE 1 (CONT'D).
10
Fen,
No,
Expression
NAND Inputs NOR
Cct. 12 3 4 5 6 7 8 9 Cct,
Inputs
123456789
66 b(a+c)+abc
67 b+ac
70 ab+ab c
71
b(a+c)+abc
72
ab+ac
73
b+ac
74
ab+ab
75
ab+ab+ac
13
c a b c a b
15
cab
8
a b a b c
13
c
a
b
cab
6
a
c
b
1J+
b
a
b
c a
12
a
c
b
b a
13
a
c
b
a b c
9
a
b
a
c
6
a
c
b
9
a
b
a
b
8
a
b
c
a b
76
ab+ab+ac
a b a b c
77
a+b
100
abc
101
c( ab+ab)
102
abc+abc
103
abc+ab
104
be
105
c ( a+b )
106
bc+abc
107
bc+ab
110
abc+abc
111
abc+abc+abc
112
ac+abc
113
a(b+c)+abc
114
b ( a+c )
115
b(a+c)+ac
116
ac+bc
1
a
b
4
a
b
3
a
b
c
2
a
b
c
7
c
a
b
c
a
b
10
a
b
a
b
c
7
a
b
c
a
b
c
15
a
b
c
a
b
c
16
a
c
b
c
a
b
8
a
b
c
a
b
14
12
a
c
b
b
c
a
a
a
b
b
4
b
c
1
b
c
6
a
b
c
5
b
a
c
8
b
c
a
b
c
14
12
c
a
b
b
a
c
c
c
b
b
9
b
c
a
b
9
b
a
b
c
7
a
b
c
8
b
c
10
a
c
a
c
b
11
a
b
c
a
b
c a b c
18
a
b
a
c
b
c a b c
8
a
c
a
b
c
14
12
a
c
c
b
a
a
b
a
c
c
13
c
b
a
c
a
b
, !3
c
b
a
c
a
b
6
c
a
b
5
c
a
b
12
c
a
b
c
a
12
a
b
c
a
b
9
a
c
b
c
9
b
c
a
c
TABLE 1 (CONT'D).
Fen.
NAND
Inputs
NOR
Inputs
No.
Expression
Cct.
1
2
3
4
5
6 7 8 9
Cct.
1
2
3
4
5 6 7 8 9
117
a+bc
5
c
b
8
6
b
c
a
120
ac
4
a
c
1
a
c
121
c ( a+b )
6
b
a
C
5
a
b
c
122
ac+abc
8
a
c
a
b
c
14
12
c
b
a
a
b
c
c
c
a
a
123
ac+ab
9
a
c
a
b
9
a
b
a
c
124
c ( a+b )
6
a
b
c
5
a
b
c
125
c
c
c
126
c(a+b)+abc
13
a
b
c
a
b
c
13
a
b
c
a
b c
127
c+ab
5
a
b
c
6
a
b
c
130
ac+abc
8
a
c
a
b
c
14
12
c
a
a
b
c
c
b
c
a
a
131
c(a+b)+abc
13
a
b
c
a
c
b
13
a
b
c
a
c b
132
ac+ac
9
a
c
a
c
9
a
c
a
c
133
ac+ac+bc
14
12
c
c
a
b
c
a
a
c
b
a
8
a
c
a
b
c
134
ac+ab
9
a
c
a
b
9
a
b
a
c
135
c+ab
5
a
b
c
6
b
a
c
136
ac+ac+bc
14
12
c
b
a
c
b
a
c
c
a
a
8
a
c
a
b
c
137
a+c
1
a
c
4
a
c
140
abc+abc
7
a
b
c
a
b
c
10
b
c
b
c
a
i4i
abc+abc+abc
11
a
b
c
a
b
c a b c
18
a
c
b
c
a b a b c
ite
bc+abc
8
b
c
a
b
c
14
12
b
c
c
a
b
b
a
b
c
c
U3
b(a+c)+abc
13
c
a
b
c
b
a
13
c
a
b
c
b a
144
bc+abc
8
b
c
a
b
c
14
12
c
b
b
a
c
c
a
c
b
b
145
c(a+b)+abc
13
b
a
c
b
c
a
13
b
a
c
b
c a
146
bc+bc
9
b
c
b
c
9
b
c
b
c
147
bc+bc+ab
14
12
b
b
c
a
b
c
c
b
a
c
8
b
c
a
b
c
UNIVERSITY Of
TABLE 1 (CONT'D) .
Fen,
NAND
Inputs
NOR
Inputs
No.
Expression
Oct.
1
2
3
k
5
6
7
8 9
Cct.
1
2
3
k
5
6 7
89
150
abc+abc+abc
11
a
b
c
a
5
c
a
b c
18
a
b
a
c
b
c a
b c
151
c ( ab+ab ) +c ( ab+ab )
17
a
b
c
b
c
a
17
a
b
c
b
c
a
152
c(a+b)+abc
13
a
b
c
c
a
b
13
a
b
c
c
a
b
153
ac+ab+bc+abc
18
a
c
a
b
b
c
a
b c
11
a
b
c
a
b
c a
b c
15^
b(a+c)+abc
13
c
a
b
b
c
a
13
c
a
b
b
c
a
155
a(b+c)+bc+abc
18
b
c
a
c
a
b
a
b c
11
a
b
c
a
b
c a
b c
156
a(b+c)+bc+bc
11+
12
b
c
c
a
b
b
c
b
a
c
8
b
c
a
b
c
157
a+bc+bc
10
b
c
b
c
a
7
b
c
a
b
c
a
160
a(b+c)
6
b
c
a
5
b
c
a
161
a(b+c)+bc
12
b
c
a
b
c
12
c
a
b
c
a
162
bc+ca
9
b
c
c
a
9
a
c
b
c
163
b+ac
5
c
a
b
6
a
c
b
164
bc+ab
9
c
b
b
a
9
a
b
b
c
165
c+ab
5
b
a
c
6
a
b
c
166
bc+bc+ab
Ik
12
b
a
c
b
a
c
b
b
c
c
8
b
c
a
b
c
167
b+c
1
b
c
k
b
c
170
a(b+c)+abc
13
b
c
a
a
b
c
13
b
c
a
a
b
c
171
a(b+c)+abc+bc
18
a
b
a
c
b
c
a
b c
11
a
b
c
a
b
c a
b c
172
b(a+c)+ac+ac
Ik
12
c
a
a
b
c
c
a
c
b
a
8
c
a
c
a
b
173
b+ac+ac
10
c
a
c
a
b
7
c
a
b
c
a
b
17^
c ( a+b ) +ab+ab
Ik
12
a
b
b
c
a
a
b
a
c
b
8
a
b
a
b
c
175
c+ab+ab
10
a
b
a
b
c
7
a
b
c
8.
b
c
176
ab+bc+ac
15
16
a
b
b
c
c
a
a
b
b
a
c
c
7
a
b
c
a
b
c
177
a+b+c
2
a
b
c

3
a
b
c
200
abc
3
a
b
c
2
a
b
c
201
abc+abc
7
a
b
c
a
b
c
15
16
a
b
b
c
c
a
a
b
b
a
c
c
TABLE 1 (CONT'D).
Fen.
NAND
Inputs
NOR
Inputs
No.
Expression
Cct.
1
2
3
1+
5 6 7
8 9
Cct,
1
2
3
1+
5
6 7
8 9
202
c ( ab+ab )
7
a
b
c
a
b c
10
a
:
a
b
c
203
abc+ab
8
a
b
a
b
c
11+
12
a
b
b
c
a
a
b
a
c
b
201+
b(ac+ac)
7
c
a
b
c
a b
10
c
a
c
a
b
205
abc+ac
8
c
a
c
a
b
11+
12
c
a
a
b
c
c
a
c
b
a
206
abc+abc+abc
11
a
b
c
a
b c a
b c
18
a
b
a
c
b
c a
b c
207
abc+a(b+c)
13
b
c
a
a
b c
13
b
c
a
a
b
c
210
be
1+
b
c
1
b
c
211
abc+bc
8
b
c
a
b
c
11+
12
b
a
c
b
a
c
b
b
c
c
212
c ( a+b )
6
a
b
c
5
b
a
c
213
ab+bc
9
a
b
b
c
9
c
b
b
a
211+
b(a+c)
6
a
c
b
5
c
a
b
215
ac+bc
9
a
c
b
c
9
b
c
c
a
216
ab+ac+bc
12
c
a
b
c
a
12
b
c
a
b
c
217
a+bc
5
b
c
a
6
b
c
a
220
a(bc+bc)
7
b
c
a
b
c a
10
b
c
b
c
a
221
abc+bc
8
b
c
a
b
c
11+
12
b
c
c
a
b
b
c
b
a
c
222
abc+abc+abc
11
a
b
c
a
b c a
b c
18
b
c
a
c
a
b a
b c
223
abc+b(a+c)
13
c
a
b
b
c a
13
c
a
b
b
c
a
221+
abc+abc+abc
11
a
b
c
a
b c a
b c
18
a
c
a
b
b
c a
b c
225
abc+c(a+b)
13
a
b
c
c
a b
13
a
b
c
c
a
b
226
ab c +ab c +ab c +ab c
17
a
b
c
b
c a
17
a
b
c
b
c
a
227
ab+ac+bc+abc
18
a
b
a
c
b c a
b c
11
a
b
c
a
b
c a
b c
230
abc+bc
8
b
c
a
b
c
11+
12
b
b
c
a
b
c
c
b
a
c
231
bc+bc
9
b
c
b
c
.
9
b
c
b
c
232
c(a+b)+abc
13
b
a
c
b
c a
13
b
a
c
b
c
a
233
bc+b(a+c)
Ik
12
c
b
b
a
c
c
a
c
b
b
8
b
c
a
b
c
TABLE 1 (CONT'D).
Fen.
No.
Expression
NAND
Cct.
1
2
3
Inputs
456789
NOR
Cct.
1
2
3
Inputs
4 5 6 7 8 9
234
b(a+c)+abc
13
c
a
b
c
b
a
13
c
a
b
c
b a
235
bc+c(a+b)
14
12
b
c
c
a
b
b
a
b
c
c
8
b
c
a
b
c
236
c(a+b)+ab+abc
18
a
c
b
c
a
babe
11
a
b
c
a
b c a b c
237
a+bc+bc
10
b
c
b
c
a
7
a
b
c
a
b c
240
ac
4
a
c
1
a
c
241
ac+abc
8
a
c
a
b
c
14
12
c
b
a
c
b
a
c
c
a
a
242
c ( a+b )
6
b
a
c
5
a
b
c
243
ab+ac
9
a
b
a
c
9
a
c
a
b
244
ac+abc
8
a
c
a
b
c
14
12
c
c
a
b
c
a
a
c
b
a
245
ac+ac
9
a
c
a
c
9
a
c
a
c
246
c(b+a)+abc
13
a
b
c
a
c
b
13
a
b
c
a
c b
247
ac+a(b+c)
14
12
c
a
a
b
c
c
b
c
a
a
8
a
c
a
b
c
250
c ( a+b )
6
a
b
c
5
a
b
c
251
c(a+b)+abc
13
a
b
c
a
b
c
13
a
b
c
a
b c
252
c
c
c
253
ab+c
5
a
b
c
6
a
b
c
254
ab+ac
9
a
b
a
c
9
a
c
a
b
255
ac+bc+ac
14
12
c
b
a
a
b
c
c
c
a
a
8
a
c
a
b
c
256
ab+c
5
a
b
c
6
b
a
c
257
a+c
l
a
c
4
a
c
260
a(b+c)
6
b
c
a
5
c
b
a
261
bc+ac
9
b
c
a
c
9
a
c
b
c
262
bc+ab+ac
12
a
b
c
a
b
12
c
a
b
c
a
263
b+ac
5
c
a
b
6
c
a
b
264
a(b+c)+abc
13
c
b
a
c
a
b
13
c
b
a
c
a b
265
ac+c(a+b)
14
12
a
c
c
b
a
a
b
a
c
c
8
a
c
a
b
c
266
a(b+c)+bc+abc
18
a
b
a
c
b
c a b c
11
a
b
c
a
b c a b c
TABLE 1 (CONT'D).
Fen.
No.
Expression
267
ac+ac+b
270
ab+bc
271
bc+ac+bc
272
ab+c
273
b+c
27^
a(b+c)+ab
NAND Inputs NOR
Cct. 12 3^56789 Cct.
Inputs
123^56789
275 a(b+c)+a(b+c)
276
ab+ab+c
277
a+b+c
300
ab
301
ab+abc
302
ab+abc
303
ab+ab
30^
b(a+c)
305
ab+ac
306
b(a+c)+abc
307
ab+a(b+c)
310
b(a+c)
311
b(a+c)+abc
312
ab+ac
313
ab+ab +bc
31k
b
315
ac+b
316
ac+b
317
a+b
320
a(b+c)
10
a
c
a
c
b
9
b
a
b
c
Ik
c
b
a
c
b
12
a
b
c
c
b
5
b
a
c
1
b
c
Ik
a
b
c
a
b
12
c
b
a
a
b
15
a
b
c
a
b
c
16
a
c
b
c
a
b
10
a
b
a
b
c
2
a
b
c
k
a
b
8
a
b
a
b
c
a b c a b
9
a
b
a
b
6
a
c
b
9
a
b
a
c
13
a
c
b
a
b
c
ll+
b
a
b
c
a
12
a
c
b
b
a
6
a
c
b
13
c
a
b
c
a
b
9
a
b
a
c
Ik
b
a
c
b
a
12
c
a
b
b
a
b
5
a
c
b
5
a
c
b
1
a
b
6
c
b
a
7
a b
cab
c
9
b c
a b
8
b c
a b c
6
a b
c
k
b c
8
a b
cab
a b c a b c
7
c
a
b
c
a
b
3
a
b
c
1
a
b
Hi
a
b
c
a
b
12
c
a
b
a
b
Ik
a
b
a
b
c
12
a
c
b
a
b
9
a
b
a
b
5
a
c
b
9
a
b
a
c
13
a
c
b
a
b
c
8
a
b
a
b
c
15
c
a
b
13
c
a
b
c
a
b
9
a
b
a
c
8
a
b
a
b
c
b
6
c
a
b
6
a
c
b
k
a
b
5
b
c
a
TABLE 1 (COM 1 '!))
16
Fen.
NAND
Inputs
NOR
Inputs
No,
Expression
Cct.
1
2
3
k
5
6789
Cct,
1
2
3
k
5 6 7 8 9
321
ab+bc
9
a
b
b
c
9
a
b
b
c
322
a(b+c)+abc
13
b
c
a
b
a
c
13
b
c
a
b
a c
323
b ( a+c ) +ab
Ik
12
a
b
b
c
a
a
c
a
b
b
8
a
b
a
b
c
32+
ac+bc+ab
12
b
c
a
b
c
12
a
b
c
a
b
325
c+ab
5
a
b
c
6
a
b
c
326
a(b+c)+bc+abc
18
a
b
a
c
b
c a b c
11
a
b
c
a
b c a b c
327
ab+ab+c
10
a
b
a
b
c
7
a
b
c
a
b c
330
ac+bc
9
b
c
a
c
9
b
c
a
c
331
ab+bc+bc
Ik
12
b
a
c
c
a
b
b
b
c
c
8
b
c
a
b
c
332
c ( a+b ) +ac
ik
12
c
b
a
a
b
c
c
c
a
a
8
c
a
b
c
a
333
c ( a+b ) +c ( a+b )
15
16
c
c
a
b
b
a
c
b
a
c
b
a
7
b
c
a
b
c a
33^
ac+b
5
c
a
b
6
a
c
b
335
b+c
1
c
b
k
b
c
336
ac+ac+b
10
c
a
c
a
b
7
b
c
a
b
c a
337
a+b+c
2
c
a
b
3
b
c
a
3+0
a(b+c)
6
b
c
a
5
b
c
a
3kL
a(b+c)+abc
13
b
c
a
b
c
a
13
b
c
a
b
c a
342
ab+bc
9
b
c
b
a
9
a
b
c
b
3^3
ab+ab+ac
Ik
12
a
c
b
b
c
a
a
a
b
b
8
a
b
a
b
c
3kk
ac+bc
9
a
c
b
c
9
b
c
a
c
3^5
ac+ab+ac
Ik
12
a
b
c
c
b
a
a
a
c
c
8
a
c
a
b
c
3+6
b(a+c)+bc
1+
12
b
a
c
c
a
b
b
b
c
c
8
b
c
a
b
c
3^7
b(a+c)+b(a+c)
15
16
b
b
c
a
a
c
b
a
c
b
a
c
7
a
b
c
a
b c
350
ab+ac+bc
12
b
c
a
b
c
12
b
c
a
b
c
TABLE L (CONT'D)
Fen,
NAND
Inputs
NOR
Inputs
No.
Expression
Cct.
1
2
3
k
5
6 7 8 9
Cct.
1
2
3
1+56789
351
ab+ac+bc+abc
18
a
b
a
c
b
c a b c
11
a
b
c
a b c a b c
352
ab+c
5
a
b
c
6
a
b
c
353
ab+ab+c
10
a
b
a
b
c
7
c
a
b
cab
35^
ac+b
5
a
c
b
6
c
a
b
355
ac+ac+b
10
a
c
a
c
b
7
b
c
a
b c a
356
b+c
1
b
c
k
b
c
357
a+b+c
2
a
b
c
3
a
b
c
360
a
a
a
361
a+bc
5
b
c
a
6
b
c
a
362
a+bc
5
b
c
a
6
c
b
a
363
a+b
1
a
b
k
a
b
364
a+bc
5
c
b
a
6
b
c
a
365
a+c
1
a
c
k
a
c
366
a+bc+bc
10
c
b
b
c
a
7
a
b
c
a b c
367
a+b+c
2
a
b
c
3
a
b
c
370
a+bc
5
b
c
a
6
b
c
a
371
a+bc+bc
10
b
c
b
c
a
7
a
b
c
a b c
372
a+c
1
a
c
k
a
c
373
a+b+c
2
a
b
c
3
a
b
c
37^
a+b
1
a
b
h
a
b
375
a+b+c
2
a
b
c
3
a
b
c
376
a+b+c
2
a
b
c
3
a
b
c
377
1
1
1
5. CIRCUIT DIAGRAMS
Circuit 1
Circuit 2
Circuit 3
L
2
^L
3
i>
^ 1
5 1
Circuit
8
Circuit 9
Circuit k
3
Circuit 5
3
Circuit 6
1
2
3
5
6
7
8
9
Circuit 10
Circuit 11
Circuit 7
3
,5
Circuit 12
18
3 
k r
5 —
6 
Circuit 13
Circuit 16
Circuit Ik
Circuit 17
Circuit 15
Circuit 1<
6. CONCLUSION.:
The results show that nearly all of the 256 functions of three
variables can be generated using four or fewer NOR or NAND elements, and that
that fanout in all circuits is one. As in Hellerman's catalog, roughly half
of the NAND circuits are those which result when the minimumOR polynomial is
rewritten in terms of the NAND connective. The analogous statement holds for
NOR circuits. It is speculated that this fraction will get smaller and smaller
as the number of variables in the function is increased. Nevertheless, the cir
cuit obtained from the minimumOR polynomial serves as a good starting point in
the search for a simple realization. One way in which the table could be used
when more variables are present would be to decompose the function and use the
circuits in the table to realize the constituents.
This catalog, along with the one by Hellerman, should prove useful in
the design of simple circuits. However, a more useful tool would be a computer
program capable of producing, in a reasonable length of time, a minimal circuit
for any arbitrary function. Perhaps such a program will be available in the
future .
20
BIBLIOGRAPHY
1. Earle, J., "Synthesizing Minimal Stroke and Dagger Functions," IRE Int.
Conv. Record , Part 2, pp. 5565; i960.
2. Hellerman, L., "A Catalog of Three Variable OR Invert and AND Invert Logical
Circuits," IEEE Trans, on Electronic Computers , Vol. EC12, pp. 198223;
June I963.
3. Maley, G. A., and J. Earle, The Logic Design of Transistor Digital
Computers , PrenticeHall, Englewood Cliffs, N.J., Chap. 6; 1963.
4. Scott, N. R., Analog and Digital Computer Technology , McGrawHill, New York,
pp. ^31^38; I960.
5. Shubert, E. J., "Logical Design by Regression," Trans. AIEE , Vol, 80
(Commun. and Electronics, No. 56), pp. 380 383; September I96I.
21
a/
JVH 2 8 1969